/**************************************************************************** **
 * Copyright (C) 2001-2020 Inhand Networks, Inc.
 **************************************************************************** **/

/* ************************************************************************** **
 *     MODULE NAME            : system
 *     LANGUAGE               : C
 *     TARGET ENVIRONMENT     : Any
 *     FILE NAME              : tree.h
 *     FIRST CREATION DATE    : 2022/05/08
 * --------------------------------------------------------------------------
 *     Version                : 1.0
 *     Author                 : EExuke
 *     Last Change            : 2022/05/08
 *     FILE DESCRIPTION       : API exported to external moduels
** ************************************************************************** */
#ifndef _TREE_H_
#define _TREE_H_

#include <stdbool.h>

/*------------------Macro Definition-------------------------*/
#define MAXITEMS    10
/*------------------End of Macro Definition------------------*/

//pet对象, 可定义为合适的类型
typedef struct item {
	char petname[20];
	char petkind[20];
} Item;

typedef struct node {
	Item item;
	struct node *left;
	struct node *right;
} Node;

typedef struct tree {
	Node *root; //指向树根的指针
	int size;   //树中的项目个数
} Tree;

/*------------------API Definition---------------------------*/
/***************************************************************************************
 * 操作   : 把一个树初始化为空树
 * 操作前 : ptree指向一个树
 * 操作后 : 该树已被初始化为空树
 ***************************************************************************************/
void InitializeTree(Tree *ptree);

/***************************************************************************************
 * 操作   : 判断树是否为空
 * 操作前 : ptree指向一个树
 * 操作后 : 该树为空返回true, 否则返回false
 ***************************************************************************************/
bool TreeIsEmpty(const Tree *ptree);

/***************************************************************************************
 * 操作   : 判断树是否已满
 * 操作前 : ptree指向一个树
 * 操作后 : 该树已满返回true, 否则返回false
 ***************************************************************************************/
bool TreeIsFull(const Tree *ptree);

/***************************************************************************************
 * 操作   : 确定树中项目的个数
 * 操作前 : ptree指向一个树
 * 操作后 : 返回树中项目的个数
 ***************************************************************************************/
int TreeItemCount(const Tree *ptree);

/***************************************************************************************
 * 操作   : 向树中添加一个项目
 * 操作前 : pi指向待添加项目，ptree指向一个已经初始化的树
 * 操作后 : 成功返回true, 否则返回false
 ***************************************************************************************/
bool AddItem(const Item *pi, Tree *ptree);

/***************************************************************************************
 * 操作   : 在树中查找一个项目
 * 操作前 : pi指向待查找的项目，ptree指向一个已经初始化的树
 * 操作后 : 找到返回true, 否则返回false
 ***************************************************************************************/
bool InTree(const Item *pi, const Tree *ptree);

/***************************************************************************************
 * 操作   : 从树中删除一个项目
 * 操作前 : pi指向待删除项目，ptree指向一个已经初始化的树
 * 操作后 : 成功返回true, 否则返回false
 ***************************************************************************************/
bool DeleteItem(const Item *pi, Tree *ptree);

/***************************************************************************************
 * 操作   : 把一个函数作用于树中每一个项目
 * 操作前 : ptree指向一个树, pfun指向一个无返回值的函数,该函数参数为Item
 * 操作后 : pfun指向的函数被作用于树中每个项目一次
 ***************************************************************************************/
void Traverse(const Tree *ptree, void (*pfun)(Item item));

/***************************************************************************************
 * 操作   : 从树中删除所有节点
 * 操作前 : ptree指向一个已经初始化的树
 * 操作后 : 该树为空树
 ***************************************************************************************/
void DeleteAll(Tree *ptree);

/*------------------End of API Definition--------------------*/

#endif /* End of _TREE_H_ */

